package com.yulan.backTrack;

import org.junit.Test;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * 40. 组合总和 II
 */
public class LeetCode_40 {

    List<List<Integer>> ans = new ArrayList<>();

    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        Arrays.sort(candidates);
        backTrace(target,new ArrayList<>(),0,candidates);
        return ans;
    }

    public void backTrace(int target , List<Integer> list ,int index , int[] arr){
        if(target == 0){
            ans.add(new ArrayList<>(list));
            return;
        }
        if(target < 0 ) return;

        for(int i = index; i<arr.length ;i++){
            if(i > index && arr[i] == arr[i-1]) continue;
            list.add(arr[i]);

            backTrace(target - arr[i] ,list,i+1,arr);

            list.remove(list.size()-1);
        }
    }

    @Test
    public void test(){
        int[] arr = {10,1,2,7,6,1,5};
        for(List<Integer> list : combinationSum2(arr,8)){
            System.out.println(list);
        }
    }
}
